1. Field of the Invention
The invention disclosed herein relates generally to network configuration protocols. More specifically, the invention relates to the standard IEEE 802.1D spanning tree protocol in virtual local area networks.
2. Related Art
A computer network typically comprises a plurality of interconnected entities. An entity may consist of any network device, such as a server or end station, that transmits or receives data frames. A common type of computer network is a local area network (“LAN”) which typically refers to a privately owned network within a single building or campus. LANs typically employ a data communication protocol, such as Ethernet or token ring, that defines the functions performed by the data link and physical layers of a communications architecture. In many instances, several LANs are interconnected by point-to-point links, microwave transceivers, satellite hook-ups, etc. to form a wide area network (“WAN”) or intranet that may span an entire country or continent.
One or more intermediate network devices are often used to couple LANs together and allow the corresponding entities to exchange information. For example, a bridge may be used to provide a bridging function between two or more LANs. Alternatively, a switch may be utilized to provide a switching function for transferring information between a plurality of LANs or end stations. Bridges and switches are devices that operate at the Data Link layer (“layer 2”) of the Open Systems Interconnection (“OSI”) model. Their operation is defined in the American National Standards Institute (“ANSI”) Institute of Electrical and Electronics Engineers (“IEEE”) 802.1D standard. A copy of the ANSI/IEEE Standard 802.1D, 1998 Edition, is incorporated by referenced herein in its entirety.
Typically, a switch (or bridge) is a computer that includes a plurality of ports that are coupled to the LANs or end stations. Ports used to couple switches to each other are generally referred to as trunk ports. Ports used to couple switches to LANs or end stations are generally referred to as access ports. The switching function includes receiving data from a sending entity at a source port and transferring that data to at least one destination port for forwarding to a receiving entity.
Switches typically learn which destination port to use in order to reach a particular entity by noting on which source port the last message originating from that entity was received. This information is then stored in a block of memory referred to as a filtering database. Thereafter, when a message addressed to a given entity is received on a source port, the switch looks up the entity in its filtering database and identifies the appropriate destination port to reach that entity. If no destination port is identified in the filtering database, the switch floods the message out all ports, except the port on which the message was received. Messages addressed to broadcast or multicast addresses are also flooded.
A computer network may be segregated into a series of logical network segments. For example, any number of physical ports of a particular switch may be associated with any number of groups within the switch by using a virtual local area network (“VLAN”) arrangement that virtually associates the port with a particular VLAN designation.
The VLAN designation for each local port is stored in a memory portion of the switch such that every time a message is received by the switch on a local port the VLAN designation of that port is associated with the message. Association is accomplished by a flow processing element which looks up the VLAN designation in the memory portion based on the local port where the message originated.
Most computer networks include redundant communications paths so that a failure of any given link or device does not isolate any portion of the network. The existence of redundant links, however, may cause the formation of loops within the network. Loops are highly undesirable because data frames may traverse the loops indefinitely. Furthermore, because switches and bridges replicate (i.e., flood) frames whose destination port is unknown or which are directed to broadcast or multicast addresses, the existence of loops may cause a proliferation of data frames that effectively overwhelms the network.
To avoid the formation of loops, many intermediate network devices execute a spanning tree algorithm that allows them to calculate an active network topology which is loop-free and yet connects every pair of VLANs within the network. The IEEE 802.1D standard defines a spanning tree protocol (“STP”) to be executed by 802.1D compatible devices (e.g., bridges, switches, and so forth). With the IEEE 802.1D STP standard, one data domain is coupled with one control domain.
In general, by executing the STP, switches elect a single switch to be the root bridge. In addition, for each VLAN coupled to more than one switch, only one (the designated bridge) is elected to forward frames to and from the respective VLAN. The designated bridge is typically the one closest to the root. Each bridge also selects one port (its “root port”) which gives the lowest cost path to the root.
The root ports and designated bridge ports are selected for inclusion in the active topology and are placed in a forwarding state so that data frames may be forwarded to and from these ports and thus onto the corresponding paths or links of the network. Ports not included within the active topology are placed in a blocking state. When a port is in the blocking state, data frames are not forwarded to or received from the port. A network administrator may also exclude a port from the spanning tree by placing it in a disabled state.
To obtain the information necessary to run the STP, switches exchange special control messages called bridge protocol data unit (“BPDU”) messages. Conventional BPDU messages contain a number of fields, including a root bridge ID (“BID”) which is the current root bridge; a path cost to the root bridge which indicates the distance to the root bridge; a sender BID which is the BID of the switch that sends the BPDU; and a port ID which is the actual port on the switch that the BPDU was sent from.
All of the switches constantly send BPDUs to each other, trying to determine the best path between various segments. When a switch receives a BPDU (from another switch) that is better than the one it is broadcasting for the same segment, it will stop broadcasting its BPDU out that segment. Instead, it will store the other switch's BPDU for reference and for broadcasting out to segments that are farther away from the root bridge.
A root bridge is chosen based on the results of the BPDU process between the switches. Initially, every switch considers itself the root bridge. When a switch first powers up on the network, it sends out a BPDU with its own BID as the root BID. When the other switches receive the BPDU, they compare the BID to the one they already have stored as the root BID. If the new root BID has a lower value, they replace the saved one. But if the saved root BID is lower, a BPDU is sent to the new switch with this BID as the root BID. When the new switch receives the BPDU, it realizes that it is not the root bridge and replaces the root BID in its table with the one it just received. The result is that the switch that has the lowest BID is elected by the other switches as the root bridge.
Based on the location of the root bridge, the other switches determine which of their ports has the lowest path cost to the root bridge. These ports are called root ports, and each switch (other than the current root bridge) must have one.
The switches determine who will have designated ports. A designated port is the connection used to send and receive packets on a specific segment. By having only one designated port per segment, all looping issues are resolved.
Designated ports are selected based on the lowest path cost to the root bridge for a segment. Since the root bridge will have a path cost of “0,” any ports on it that are connected to segments will become designated ports. For the other switches, the path cost is compared for a given segment. If one port is determined to have a lower path cost, it becomes the designated port for that segment. If two or more ports have the same path cost, then the switch with the lowest BID is chosen.
Once the designated port for a network segment has been chosen, any other ports that connect to that segment become non-designated ports. These non-designated ports block network traffic from taking that path so it can only access that segment through the designated port.
Each switch has a table of BPDUs that it continually updates. The network is now configured as a single spanning tree, with the root bridge as the trunk and all the other switches as branches. Each switch communicates with the root bridge through the root ports, and with each segment through designated ports, thereby maintaining a loop-free network.
In response to network changes or failures, BPDU information is up-dated, and/or it times-out and causes the active spanning tree topology to be re-calculated. As a result, ports may transition from the blocking state to the forwarding state and vice versa. When a topology change is detected, the IEEE 802.1D STP standard moves the ports into fast-aging mode. This means that the Media Control Access (“MAC”) addresses learned on those ports age (or transition from one state to another) at a faster rate (5 times) than normal MAC aging. That is, as a result of new BPDU information, a previously blocked port may learn that it should be in the forwarding state (e.g., it is now the root port or a designated port). Rather than transition directly from the blocking state to the forwarding state, ports typically transition through two intermediate states: a listening state and a learning state. In the listening state, a port waits for information indicating that it should return to the blocking state. If, by the end of a preset time, no such information is received, the port transitions to the learning state. At the end of a second preset time, the port transitions from the learning state to the forwarding state, thereby allowing data frames to be forwarded to and from the port.
As mentioned above, the IEEE 802.1D STP standard maintains one control domain. This happens because the VLAN to STP instance is unique. A port in the VLAN is automatically included in the single STP instance associated to that VLAN (there is a one-to-one mapping). Thus, the IEEE 802.1D STP standard suffers from several limitations when implemented in multiple large interconnected networks. The standard STP is prone to slow convergence times, sometimes upward of 30 to 50 seconds, and does not scale well as a topology expands to include additional spanning tree nodes. Additionally, the spanning tree domain (or control domain) must be continuous in order to ensure a loop free data path—changes within the spanning tree domain can affect all spanning tree members of that domain. Such ripple effects, for example, can cause problems in one city to affect other cites where large metro ring topologies are implemented.